//1.回溯
class Solution {
public:
    static const int N = 20;
    int col[N] = {0}, zhu[N] = {0}, fu[N] = {0}; // 扩展数组大小
    vector<pair<int, int>> temp; // 存储所有皇后的坐标
    vector<string> rret; // 存储当前棋盘状态
    
    void dfs(vector<vector<string>>& act, int i, int n) {
        if (i > n) { // 找到一个解
            // 初始化棋盘
            rret.assign(n, string(n, '.')); // 正确初始化rret
            
            // 设置皇后位置
            for (auto& p : temp) {
                int row = p.first - 1; // 存储的起始为1，rret默认还是0,所以-1
                int col = p.second - 1;
                rret[row][col] = 'Q';
            }
            
            act.push_back(rret);
            return;
        }
        
        for (int j = 1; j <= n; ++j) {
            if (col[j] || fu[i+j] || zhu[n-j+i]) continue;
            
            // 选择当前位置
            col[j] = 1;
            fu[i+j] = 1;
            zhu[n-j+i] = 1;
            temp.push_back({i, j});
            
            dfs(act, i+1, n);
            
            // 回溯
            col[j] = 0;
            fu[i+j] = 0;
            zhu[n-j+i] = 0;
            temp.pop_back();
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ret;
        dfs(ret, 1, n);
        return ret;
    }
};









